Stepen $n$ se može predstaviti kao zbir stepena broja 2.
Npr. $25 = 2^0 + 2^3 + 2^4$ ili u binarnom zapisu $(11001)_2$ Zatim, vrednost $a^{25} = a^{(2^0) + (2^3) + (2^4)} = a^{(2^0)} * a^{(2^3)} * a^{(2^4)} = a^{1} * a^{8} * a^{16}$.
Za svaku jedinicu na poziciji $i$ binarnog zapisa stepena $n$ vrednost $a^{n}$ je jednaka $a^{(2^i)}$. Jedinica na sledećoj poziciji u binarnom zapisu stepena $n$ daje vrednost stepena $a^{(2^{i+1})}$ koja se dobija kao kvadrat prethodne vrednosti $a^{(2^i)}$.
Zaista, $(a^{(2^i)})^2 = a^{(2^{i} * 2)} = a^{(2^{i+1})}$
def mod_pow(a, n, m):
a = a % m
res = 1
while n > 0:
if n % 2 == 1: # Za svaku jedinicu u binarnom zapisu n
res = (res * a) % m # Rezultat je stara vrednost rezultata * a^2{i} za i-tu poziciju
a = (a * a) % m
n = n // 2 # n gubi poslednju cifru u binarnom zapisu (može i kao logičko šiftovanje udesno)
return res
a = 3
n = 25
m = 17
print(f'Rezultat naše mod_pow funkcije: {mod_pow(a, n, m)}')
print(f'Rezultat pow funkcije iz python biblioteke: {pow(a, n, m)}')